package jointPart_4_Hashtable;



public class DynamicHash {
    private Word[] array;
    private int noElements = 0;
    private int resized = 0;

    /**
     * Default constructor. Allocates 10 elements
     * at the beginning and calls the resize method
     * if the load factor becomes bigger than 0.75
     */
    public DynamicHash() {
        array = new Word[10];
    }

    /**
     * Put a word in the hash and append the URL to
     * its list of URLs. Creates the word if it does
     * not already exist
     *
     * @param word The word to add
     * @param url  The URL were the word was found
     */
    public void put(String word, String url) {
        if (word == null || word.isEmpty())
            return;

        // Calculate a valid hash code
        int hashCode = Math.abs(word.hashCode()) % array.length;

        if (array[hashCode] == null) {
            // There is nothing at this index, so create a new entry
            Word w = new Word(word);
            w.urls = new URLlist(url);
            array[hashCode] = w;
            // We now have one more element in the hash
            ++noElements;
        } else {
            // There is already something here, so check if
            // the word is already there
            Word current = array[hashCode];
            boolean doesExist = false;

            // Loop until we reach the end of the list (i.e.
            // the next element is null)
            while (current != null) {
                if (current.word.equals(word)) {
                    doesExist = true;
                    break;
                }

                current = current.next;
            }

            if (!doesExist) {
                // The word does not already exist, so create it
                Word w = new Word(word);
                w.urls = new URLlist(url);

                // The following two lines appends the new entry
                // onto the start just like we did in the previous
                // assignment
                w.next = array[hashCode];
                array[hashCode] = w;
                ++noElements;
            } else {
                // The word already exists, try and add the url
                // Note that we don't increment the noElements
                // instance variable because we are not adding
                // another 'Word' object (it already exists), but
                // just appending the URL if it is not already there

                // There is no URLs associated with the entry, so add it
                if (current.urls == null)
                    current.urls = new URLlist(url);
                else {
                    // There are already some URLs associated with the entry
                    // Check if the one we are adding is already there
                    URLlist currentUrl = current.urls;

                    while (currentUrl != null) {
                        // The URL already exists, so we can just return
                        if (currentUrl.url.equals(url))
                            return;

                        currentUrl = currentUrl.next;
                    }

                    // Add the URL in the same way we add 'Word' objects
                    URLlist urlNode = new URLlist(url);
                    urlNode.next = current.urls;
                    current.urls = urlNode;
                }
            }
        }

        // Resize if necessary
        if (loadFactor() > 0.75f)
            resize();
    }

    /**
     * Retrieve the linked list of URLs for the
     * given word
     *
     * @param word The word to retrieve the URLs for
     * @return Returns a linked list of URLs or null if
     *         the word was not found
     */
    public URLlist getURLlist(String word) {
        int hashCode = Math.abs(word.hashCode()) % array.length;

        if (array[hashCode] == null)
            return null;

        Word current = array[hashCode];

        while (current != null) {
            if (current.word.equals(word))
                return current.urls;

            current = current.next;
        }

        return null;
    }

    /**
     * Retrieve a String of the URLs for a
     * given word separated by newlines
     *
     * @param word The word to retrieve the URLs for
     * @return A String containing the URLs or an
     *         empty String
     */
    public String getURLs(String word) {
        URLlist urlList = getURLlist(word);

        if (urlList == null)
            return "";

        String urls = "";

        while (urlList != null) {
            urls += urlList.url + "\n";
            urlList = urlList.next;
        }

        // Return the string with trailing (and leading) whitespace removed
        return urls.trim();
    }

    /**
     * Tests whether or not 'word' exists in the
     * hash
     *
     * @param word The word in question
     * @return If the word exists in the hash or not
     */
    public boolean contains(String word) {
        int hashCode = Math.abs(word.hashCode()) % array.length;

        if (array[hashCode] == null)
            return false;

        Word current = array[hashCode];

        while (current != null) {
            if (current.word.equals(word))
                return true;

            current = current.next;
        }

        return false;
    }

    /**
     * Print all keys and their values
     */
    public void printKeyValuePairs() {
        for (int i = 0; i < array.length; ++i) {
            if (array[i] == null)
                continue;

            Word current = array[i];

            while (current != null) {
                System.out.println("Key => " + current.word);

                URLlist url = current.urls;

                while (url != null) {
                    System.out.println("\t" + url.url);
                    url = url.next;
                }

                current = current.next;
            }
        }
    }

    /**
     * Get the number of elements currently stored
     * in the hash
     *
     * @return The number of elements stored in the hash
     */
    public int noElements() {
        return noElements;
    }

    // Equation: (number of total elements stored / length of array)
    // Not sure if the numerator should be the above or just the
    // number of non-empty entries in the hash
    /**
     * Gets the load factor for the hash
     *
     * @return The load factor
     */
    public float loadFactor() {
        return ((float)noElements / (float)array.length);
    }

    /**
     * Resizes the internal array used for hashing if
     * the load factor becomes bigger than 0.75 by
     * doubling the size of the array and copying
     * all the elements to the new array
     */
    private void resize() {
        // Create a new array twice the size of the old one
        Word[] newArray = new Word[array.length * 2];

        // Copy all the old entries to the new table
        for (int i = 0; i < array.length; ++i) {
            if (array[i] == null)
                continue;

            Word current = array[i];

            while (current != null) {
                int hashCode = Math.abs(current.word.hashCode() % newArray.length);

                if (newArray[hashCode] == null) {
                    newArray[hashCode] = current;
                } else {
                    Word w = new Word(current);
                    w.next = newArray[hashCode];
                    newArray[hashCode] = w;
                }
                
                current = current.next;
            }
        }

        array = newArray;
        ++resized;
    }

    /**
     * Gets the number of times the hash was resized
     *
     * @return The resize count
     */
    public int noResized() {
        return resized;
    }
}